/* split an array into several slices
 * when each slice is sorted, the whole array is sorted
 * e.g.
 * [4,3,1,6,5,9,8] into [4,3,1], [6,5], [9,8]
 * [4,3,6,5,9,8,1] can not be split because no way to make sure the array is sorted
*/

#include "leetcode_util.h"

int solution_help(vector<int> &A, int start, int len_A, int not_less_than, map<int, int>& result_map) {
    if (start >= len_A) return 0;
    if (A[start] < not_less_than) return 0;
    if (result_map.count(start) != 0) return result_map[start];
    if (start == len_A - 1) {
        if (A[start] <= not_less_than) {
            result_map[start] = 0;
            return 0;
        } else {
            result_map[start] = 1;
            return 1;
        }
    }
    int nlt = A[start];
    for (int i = start+1; i < len_A; i++) {
        if (A[i] <= not_less_than) {
            result_map[start] = 0;
            return 0;
        }
        if (A[i] <= nlt) continue;
        int res = solution_help(A, i, len_A, nlt, result_map);
        if (res != 0) {
            result_map[start] = res + 1;
            return res + 1;
        }
        if (A[i] > not_less_than) {
            not_less_than = A[i];
        }
    }
    result_map[start] = 0;
    return 1;
}

int solution1(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    vector<int> results{1};
    int max_res = 0;
    int not_less_than = A[0];
    int len_A = A.size();
    if (len_A == 1) return 1;
    map<int, int> result_map;
    for (int i = 1; i < len_A; i++) {
        if (A[i] <= not_less_than) continue;
        results.push_back(solution_help(A, i, len_A, not_less_than, result_map) + 1);
        if (A[i] > not_less_than) {
            not_less_than = A[i];
        }
    }
    for (auto res : results) {
        if (res > max_res) {
            max_res = res;
        }
    }
    return max_res;
}

// 30, 26, 24, 2, 32, 34, 20, 38, 50, 48, 33
// when we concatenate the subarrays, the whole array should be sorted
// So an array can be split only when
// 1. index of min < index of max
// 2. element in the right subarray is larger than the max of the left
int helper2(vector<int> &A, int s, int l, int not_less_than) {
    // any one is smaller than the max from the left, illegal trial
    auto min_itr = min_element(A.begin()+s, A.end());
    if (*min_itr < not_less_than) return 0;
    // min is at the right of max, can not split
    auto max_itr = max_element(A.begin()+s, A.end());
    if (min_itr > max_itr) return 1;

    auto max_min_left = max_element(A.begin()+s, min_itr+1);
    auto min_max_right = min_element(max_itr, A.end());
    // any one from the right of max is smaller than the max from the left
    // can not split
    if (*max_min_left > *min_max_right) return 1;

    // try to split into [x,...min],[min+1,...]
    int new_s = min_itr - A.begin() + 1;
    // update the new start point if any one is smaller than the max from the left
    for (int i = new_s; i < max_itr - A.begin(); ++i) {
        if (A[i] < *max_min_left) new_s = i + 1;
    }
    // the new start point is the max
    // as we have check the elements in the right of max
    // the array can be split into [x,...,<before max>],[max,...]
    if (max_itr - (A.begin() + new_s) == 0) return 2;
    int max_lest = *max_element(A.begin()+s, A.begin()+new_s);
    // finally, try [x,...,<new start>],[y,...<including max>,...]
    return 1 + helper2(A, new_s, l, max_lest);
}

int solution2(vector<int> &A) {
    int l = A.size();
    return helper2(A, 0, l, 0);
}

void showVector(vector<int>& A) {
    vector<int>::iterator itr = A.begin();
    for(; itr != A.end();) {
        printf("%d", *itr);
        if (++itr != A.end()) {
            printf(" ");
        } else {
            printf("\n");
        }
    }
}

void testVector(int argc, char *argv[]) {
    string s;
    for (int i = 1; i < argc; i++) {
        s = string(argv[i]);
        vector<int> v = stringToVector(s);
        // test function

    }
}

vector<int> generateRandomVector(int N, int limit, bool uniq) {
    srand (time(NULL));
    set<int> s;
    vector<int> v(N, 0);
    for (int i = 0; i < N;) {
        int r = rand() % limit + 1;
        if (uniq) {
            if (s.count(r) == 0) {
                s.insert(r);
            } else {
                continue;
            }
        }
        v[i++] = r;
    }
    return v;
}

int main(int argc, char *argv[]) {
    //vector<int> v = generateRandomVector(10, 30, true);
    //vector<int> v{4,3,8,7,10,9,18,13};
    //vector<int> v{9, 16, 7, 18, 8, 20};
    //vector<int> v{30, 6, 28, 20, 15, 13, 26, 8, 19, 1};
    vector<int> v{30, 26, 24, 2, 32, 34, 20, 38, 50, 48};
    srand (time(NULL));
    //if (rand() % 2 == 1) sort(v.begin(), v.end());
    showVector(v);
    int result;
    clock_t c_start = clock();
    for (int i = 0; i < 10000; ++i) {
        result = solution1(v);
    }
    cout << "solution1: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    c_start = clock();
    for (int i = 0; i < 10000; ++i) {
        result = solution2(v);
    }
    cout << "solution2: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    /*
    c_start = clock();
    for (int i = 0; i < 10000; ++i) {
        result = solution3(v, 6);
    }
    cout << "solution3: " << result << " - " << float( clock () - c_start ) /  CLOCKS_PER_SEC << endl;
    */
}

